/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-19 11:10:35
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-22 23:17:03
 * @FilePath: \LeetCode\279.完全平方数.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=279 lang=cpp
 *
 * [279] 完全平方数
 * 
 * 注意：打表数组 int squareNums[100] 应放入成员函数 -> 影响整体运行效率计算
 *
 * 方法1：动态规划 O(n \sqrt{n})
 * - 状态 dp[i]：和为 i 的完全平方数的最少数量
 * - 状态转移方程：dp[i] = min{dp[i - j^2]} + 1 , j=1,2,3,...
 * - n <= 10^4 dp规模过大 -> 官方题解类似
 *
 * 方法2：对完全平方数 squareNums 进行 BFS 得到最短路径
 * - 最先得到的结果即为最小值
 */

#include <vector>
#include <queue>
#include <cmath>
#include <iostream>

// 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9409, 9604, 9801, 10000,

// @lc code=start
class Solution
{
public:
    /* 完全平方数 squareNums[i-1] = i^2 */
    int squareNums[100] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9409, 9604, 9801, 10000};

    int numSquares_01(int n)
    {
        if (squareNums[static_cast<int>(sqrt(n)) - 1] == n)
            return 1;

        std::vector<int> minSumDP(n + 1); // 和为 i 的完全平方数的最少数量
        for (int i = 1; i <= n; i++)
        {
            int minDP = std::numeric_limits<int>::max(); // min{dp[i - j^2]}
            for (int j = 0; squareNums[j] <= i; j++)
                minDP = std::min(minDP, minSumDP[i - squareNums[j]]);
            /* dp[i] = min{dp[i - j^2]} + 1 */
            minSumDP[i] = minDP + 1;
        }

        return minSumDP[n];
    }

    int numSquares_02(int n)
    {
        int rootN = sqrt(n); // squareNums[rootN - 1] <= n
        if (squareNums[rootN - 1] == n)
            return 1;

        /* 完全平方数和 + 层级 */
        std::queue<std::pair<int, int>> squareSumsQue;
        squareSumsQue.push({0, 0});

        while (!squareSumsQue.empty())
        {
            auto current = squareSumsQue.front();
            squareSumsQue.pop();

            /* 贪心 尽可能找较大的数 */
            for (int i = rootN - 1; i >= 0; i--)
            {
                int sum = current.first + squareNums[i];
                if (sum == n) // BFS 最短路径
                    return current.second + 1;
                else if (sum < n)
                    squareSumsQue.push({sum, current.second + 1});
            }
        }

        return rootN;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;

    // std::cout << solution.numSquares(10000) << std::endl;

    return 0;
}